#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
// #include"snake.h"
using namespace std;


#define max_size 20

class Snake{
public:
    int head_low;
    int head_upp;
    int tail_low;
    int tail_upp;
    int length;
    int snake[max_size][max_size];
    Snake(int low = 1, int upp = 1, int len = 3);
    void moveHead(string direction);
    bool ifEatFood(int food_low, int food_upp);
    void eatFood();
    void addTail();
    void tailMove();
    bool isEnd(string nextDir);
    bool tailOut();
    void print(int food_low, int food_upp);
    void GreateGraphFromFile(Snake& s);
};


//创建地图并移动尾巴
Snake::Snake(int low, int upp, int len):tail_low(low), tail_upp(upp), length(len){
    // for(int i = 0;i < max_size;i++){
    //     for(int j = 0;j < max_size;j++){
    //         snake[i][j] = 0;
    //     }
    // }
    GreateGraphFromFile(*this);
    for(int i = 0;i < length;i++){
        snake[low + i][upp] = i + 1;
    }
    head_low = tail_low + length - 1;
    head_upp = tail_upp;
}
//移动尾巴
void Snake::tailMove(){
    if(tail_upp < max_size && snake[tail_low][tail_upp + 1] == snake[tail_low][tail_upp] + 1){
        snake[tail_low][tail_upp] = 0;
        tail_upp += 1;
        return;
    }
    if(tail_low < max_size && snake[tail_low + 1][tail_upp] == snake[tail_low][tail_upp] + 1){
        snake[tail_low][tail_upp] = 0;
        tail_low += 1;
        return;
    }
    if(tail_low > 0 && snake[tail_low - 1][tail_upp] == snake[tail_low][tail_upp] + 1){
        snake[tail_low][tail_upp] = 0;
        tail_low -= 1;
        return;
    }
    if(tail_upp > 0 && snake[tail_low][tail_upp - 1] == snake[tail_low][tail_upp] + 1){
        snake[tail_low][tail_upp] = 0;
        tail_upp -= 1;
        return;
    }
}
//移动蛇头
void Snake::moveHead(string direction){
    // switch(direction){
    //     case 4: snake[head_low][head_upp - 1] = snake[head_low][head_upp] + 1;
    //         head_upp -= 1;
    //         break;
    //     case 2: snake[head_low + 1][head_upp] = snake[head_low][head_upp] + 1;
    //         head_low += 1;
    //         break;
    //     case 6: snake[head_low][head_upp + 1] = snake[head_low][head_upp] + 1;
    //         head_upp += 1;
    //         break;
    //     case 8: snake[head_low - 1][head_upp] = snake[head_low][head_upp] + 1;
    //         head_low -= 1;
    //         break;
            
    // }

    if(direction == "a"){
        snake[head_low][head_upp - 1] = snake[head_low][head_upp] + 1;
        head_upp -= 1;
    }else if(direction == "s"){
        snake[head_low + 1][head_upp] = snake[head_low][head_upp] + 1;
        head_low += 1;
    }else if(direction == "d"){
        snake[head_low][head_upp + 1] = snake[head_low][head_upp] + 1;
        head_upp += 1;
    }else if(direction == "w"){
        snake[head_low - 1][head_upp] = snake[head_low][head_upp] + 1;
        head_low -= 1;
    }
}
//增长尾部
void Snake::addTail(){
    if(tail_upp < max_size && snake[tail_low][tail_upp + 1] == snake[tail_low][tail_upp] + 1){
        snake[tail_low][tail_upp - 1] = snake[tail_low][tail_upp] - 1;
        tail_upp -= 1;
        return;
    }
    if(tail_low < max_size && snake[tail_low + 1][tail_upp] == snake[tail_low][tail_upp] + 1){
        snake[tail_low - 1][tail_upp] = snake[tail_low][tail_upp] - 1;
        tail_low -= 1;
        return;
    }
    if(tail_low > 0 && snake[tail_low - 1][tail_upp] == snake[tail_low][tail_upp] + 1){
        snake[tail_low + 1][tail_upp] = snake[tail_low][tail_upp] - 1;
        tail_low += 1;
        return;
    }
    if(tail_upp > 0 && snake[tail_low][tail_upp - 1] == snake[tail_low][tail_upp] + 1){
        snake[tail_low][tail_upp + 1] = snake[tail_low][tail_upp] - 1;
        tail_upp += 1;
        return;
    }
}
//判断是否吃到食物
bool Snake::ifEatFood(int food_low, int food_upp){
    return snake[food_low][food_upp] > 0;
}
//吃到食物后尾部增长
void Snake::eatFood(){
    length ++;
    for(int i = 0;i < max_size;i++){
        for(int j = 0;j < max_size;j++){
            if(snake[i][j] > 0){
                snake[i][j] ++;
            }
        }
    }
    addTail();
}
//判断是否结束
bool Snake::isEnd(string nextDir){
    int upp = head_upp, low = head_low;
    // switch(nextDir){
    //     case 4: upp = head_upp - 1;
    //         break;
    //     case 2: low = head_low + 1;
    //         break;
    //     case 6: upp = head_upp + 1;
    //         break;
    //     case 8: low = head_low - 1;
    //         break;
    // }
    if(nextDir == "a"){
        upp = head_upp - 1;
    }else if(nextDir == "s"){
        low = head_low + 1;
    }else if(nextDir == "d"){
         upp = head_upp + 1;
    }else if(nextDir == "w"){
        low = head_low - 1;
    }
    if(!(upp >=0 && upp < max_size)){
        return true;
    }
    if(!(low >= 0 && low < max_size)){
        return true;
    }
    return snake[low][upp] > 0;
}
//判断蛇尾是否超出地图
bool Snake::tailOut(){
    if(!(tail_upp >=0 && tail_upp < max_size)){
        return true;
    }
    if(!(tail_low >= 0 && tail_low < max_size)){
        return true;
    }
    return false;
}
//将地图跟蛇一起打印
void Snake::print(int food_low, int food_upp){
    // for(int i = -1;i < max_size + 1;i++){
    //     cout << "#";
    // }
    // cout << endl;
    // for(int i = 0;i < max_size;i++){
    //     cout << "#";
    //     for(int j = 0;j < max_size;j++){
    //         if(snake[i][j] > 0){
    //             if(i == head_low && j == head_upp){
    //                 cout << "H";
    //             }
    //             else if(i == tail_low && j == tail_upp){
    //                 cout << "T";
    //             }
    //             else{
    //                 cout << "*";
    //             }
    //         }
    //         else if(i == food_low && j == food_upp){
    //             cout << "@";
    //         }
    //         else{
    //             cout << " ";
    //         }
    //     }
    //     cout << "#\n";
    // }
    // for(int i = -1;i < max_size + 1;i++){
    //     cout << "#";
    // }
    // cout << endl;

    for(int i = 0;i < max_size;i++){
        for(int j = 0;j < max_size;j++){
            if(snake[i][j] > 0){
                if(i == head_low && j == head_upp){
                    cout << "H";
                }
                else if(i == tail_low && j == tail_upp){
                    cout << "T";
                }
                else{
                    cout << "*";
                }
            }
            else if(i == food_low && j == food_upp){
                cout << "@";
            }
            else if(snake[i][j] == -1){
                cout << "#";
            }
            else{
                cout << " ";
            }
        }
        cout << endl;
    }
}


void Snake::GreateGraphFromFile(Snake& snake){
    string s;
    ifstream inf;
    inf.open("./graph.txt");
    for(int i = 0;i < max_size;i++){
        getline(inf,s);
        for(int j = 0;j < max_size;j++){
            if(s[j] == '*'){
                snake.snake[i][j] = -1;
            }
            else{
                snake.snake[i][j] = 0;
            }
        }
    }
    // for(int i = 0;i < max_size;i++){
    //     for(int j = 0;j < max_size;j++){
    //         cout << snake.snake[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    inf.close();
}

int map[max_size][max_size];
int known[max_size][max_size];

int dfs(int curr_x,int curr_y,int food_x,int food_y){
    // cout << "(" << curr_x <<  ", " << curr_y << ")" << endl;
    // for(int i = 0;i < max_size;i++){
    //     for(int j = 0;j < max_size;j++){
    //         if(i == curr_x && j == curr_y){
    //             cout << "H";
    //         }
    //         else if(i == food_x && j == food_y){
    //             cout << "@";
    //         }
    //         else if(map[i][j] == -1){
    //             cout << "#";
    //         }
    //         else{
    //             cout << " ";
    //         }
    //     }
    //     cout << endl;
    // }
    if(curr_x == food_x && curr_y == food_y){
        cout << "eat food" << endl;
        return 1;
    } 
    
    if(known[curr_x][curr_y]){
        return 999999;
    }
    else{
        known[curr_x][curr_y] = 1;
    }
    if(map[curr_x][curr_y] < 0){
        // cout << "return 99999" << endl;
        return 999999;
    }

    vector<int> res;
    if((curr_x+1 == food_x && curr_y==food_y) || (map[curr_x+1][curr_y] == 0)){
        int dis_down = dfs(curr_x+1,curr_y,food_x,food_y);
        if(dis_down == 1){
            return 2;
        }
        res.push_back(dis_down);
    }
    if((curr_x-1 == food_x && curr_y==food_y) || (map[curr_x-1][curr_y] == 0)){
        int dis_up = dfs(curr_x-1,curr_y,food_x,food_y);
        if(dis_up == 1){
            return 2;
        }
        res.push_back(dis_up);
    }
    if((curr_x == food_x && curr_y-1==food_y) || (map[curr_x][curr_y-1] == 0)){
        int dis_left = dfs(curr_x,curr_y-1,food_x,food_y);
        if(dis_left == 1){
            return 2;
        }
        res.push_back(dis_left);
    }
    if((curr_x == food_x && curr_y+1==food_y) || (map[curr_x][curr_y+1] == 0)){
        int dis_right = dfs(curr_x,curr_y+1,food_x,food_y); 
        if(dis_right == 1){
            return 2;
        }   
        res.push_back(dis_right);
    }

    // s

    if(res.size() == 0){
        cout << "bug" << endl;
    }

    sort(res.begin(),res.end());
    // cout << "min dis:" << res[0] << endl;
    // for(int i = 0;i < res.size();i++){
    //     cout << res[i] << " ";
    // }
    // cout << endl;

    return res[0]+1;
}

int main(){
    Snake t_snake;
    // GreateGraphFromFile(t_snake);
    srand(time(0));
    int food_low,food_upp;
    while(true){
        food_low = rand() % (max_size - 2) + 1;
        food_upp = rand() % (max_size - 2) + 1;
        int status = t_snake.snake[food_low][food_upp];
        if(status != -1 && !(food_low==1 && (food_upp >= 1 || food_upp <= 3))){
            break;
        }
    }
    t_snake.print(food_low, food_upp);//打印出初始蛇
    int path[max_size][max_size];
    for(int i = 0;i < max_size;i++){
        for(int j = 0;j < max_size;j++){
            path[i][j] = 0;
        }
    }
    while(true){
        string direction;
        // cout << "方向键为‘S’-‘下’， ‘W’-‘上’， ’A‘-’左‘， ’D‘-’右‘" << endl;
        // cout << "各位大佬不要做一些奇奇怪怪的操作，程序不完善，跑出问题概不负责（比如不要往回走，故意走过墙什么的）" << endl;
        // cout << "方向";
        int curr_x = t_snake.head_low;
        int curr_y = t_snake.head_upp;

        for(int i = 0;i < max_size;i++){
            for(int j = 0;j < max_size;j++){
                map[i][j] = t_snake.snake[i][j];
                known[i][j] = 0;
            }
        }

        // // cout << "1";
        // int dis_down = dfs(curr_x+1,curr_y,food_low,food_upp,"s");
        // // cout << "2";
        // int dis_up = dfs(curr_x-1,curr_y,food_low,food_upp,"w");
        // // cout << "3";
        // int dis_left = dfs(curr_x,curr_y-1,food_low,food_upp,"a");
        // // cout << "4";
        // int dis_right = dfs(curr_x,curr_y+1,food_low,food_upp,"d");
        // // cout << "5";
        int dis_down = 999999999;
        int dis_up = 999999999;
        int dis_left = 999999999;
        int dis_right = 999999999;
        if(((curr_x+1 == food_low && curr_y==food_upp) || (map[curr_x+1][curr_y] == 0)) && path[curr_x+1][curr_y] == 0){
            dis_down = dfs(curr_x+1,curr_y,food_low,food_upp);
        }
        if(((curr_x-1 == food_low && curr_y==food_upp) || (map[curr_x-1][curr_y] == 0)) && path[curr_x-1][curr_y] == 0){
            dis_up = dfs(curr_x-1,curr_y,food_low,food_upp);
        }
        if(((curr_x == food_low && curr_y-1==food_upp) || (map[curr_x][curr_y-1] == 0)) && path[curr_x][curr_y-1] == 0){
            dis_left = dfs(curr_x,curr_y-1,food_low,food_upp);
        }
        if(((curr_x == food_low && curr_y+1==food_upp) || (map[curr_x][curr_y+1] == 0)) && path[curr_x][curr_y+1] == 0){
            dis_right = dfs(curr_x,curr_y+1,food_low,food_upp);    
        }
        cout << "down:" << dis_down << endl;
        cout << "up:" << dis_up << endl;
        cout << "left:" << dis_left << endl;
        cout << "right:" << dis_right << endl;
        char tmp;
        cin >> tmp;

        if(dis_down < dis_up){
            if(dis_left < dis_right){
                if(dis_down < dis_left){
                    direction = "s";
                }
                else{
                    direction = "a";
                }
            }
            else{
                if(dis_down < dis_right){
                    direction = "s";
                }
                else{
                    direction = "d";
                }
            }
        }
        else{
            if(dis_left < dis_right){
                if(dis_up < dis_left){
                    direction = "w";
                }
                else{
                    direction = "a";
                }
            }
            else{
                if(dis_up < dis_right){
                    direction = "w";
                }
                else{
                    direction = "d";
                }
            }
        }

        if(direction=="s"){
            path[curr_x+1][curr_y] = 1;
        }
        else if(direction=="w"){
            path[curr_x-1][curr_y] = 1;
        }
        else if(direction=="a"){
            path[curr_x][curr_y-1] = 1;
        }
        else{
            path[curr_x][curr_y+1] = 1;
        }
        cout << direction << endl;
        if(t_snake.isEnd(direction)){
            cout << "碰到墙或者吃到自己了" << endl;
            break;
        }
        t_snake.moveHead(direction);
        t_snake.tailMove();
        if(t_snake.tailOut()){
            cout << "尾巴出去了" << endl;
            break;
        }
        if(t_snake.ifEatFood(food_low, food_upp)){
            food_low = rand() % max_size;
            food_upp = rand() % max_size;
            t_snake.eatFood();
            for(int i = 0;i < max_size;i++){
                for(int j = 0;j < max_size;j++){
                    path[i][j] = 0;
                }
            }
        }
        t_snake.print(food_low, food_upp);
    }
    cout << "Game Over" << endl;
    return 0;
}
